import copy
from typing import List


def partition(s: str) -> List[List[str]]:
    def isValid(string: str):
        i = 0
        j = len(string) - 1
        while i < j:
            if string[j] != string[i]:
                return False
            i += 1
            j -= 1
        return True

    path = []
    result = []

    def backtracking(start_index):
        if start_index >= len(s):
            result.append(copy.copy(path))
            return
        # 选择一个终止位置
        for j in range(start_index, len(s)):
            if not isValid(s[start_index:j + 1]): continue
            path.append(s[start_index:j + 1])
            backtracking(j + 1)
            path.pop()

    backtracking(0)
    return result


if __name__ == '__main__':
    r = partition('aab')
    print(r)
